use std::cmp::min;
use std::mem;

/// A trait representing a hash function for the Bloom filter.
pub trait HashFunction {
    fn hash(&self, value: &[u8]) -> u32;
}

/// A Bloom filter implementation in Rust.
pub struct BloomFilter<H: HashFunction> {
    hash_func: H,
    table: Vec<u8>,
    table_size: usize,
    num_functions: usize,
}

/// Salt values used to generate multiple unique hashes.
const SALTS: [u32; 64] = [
    0x1953c322, 0x588ccf17, 0x64bf600c, 0xa6be3f3d, 0x341a02ea, 0x15b03217, 0x3b062858, 0x5956fd06,
    0x18b5624f, 0xe3be0b46, 0x20ffcd5c, 0xa35dfd2b, 0x1fc4a9bf, 0x57c45d5c, 0xa8661c4a, 0x4f1b74d2,
    0x5a6dde13, 0x3b18dac6, 0x05a8afbf, 0xbbda2fe2, 0xa2520d78, 0xe7934849, 0xd541bc75, 0x09a55b57,
    0x9b345ae2, 0xfc2d26af, 0x38679cef, 0x81bd1e0d, 0x654681ae, 0x4b3d87ad, 0xd5ff10fb, 0x23b32f67,
    0xafc7e366, 0xdd955ead, 0xe7c34b1c, 0xfeace0a6, 0xeb16f09d, 0x3c57a72d, 0x2c8294c5, 0xba92662a,
    0xcd5b2d14, 0x743936c8, 0x2489beff, 0xc6c56e00, 0x74a4f606, 0xb244a94a, 0x5edfc423, 0xf1901934,
    0x24af7691, 0xf6c98b25, 0xea25af46, 0x76d5f2e6, 0x5e33cdf2, 0x445eb357, 0x88556bd2, 0x70d1da7a,
    0x54449368, 0x381020bc, 0x1c0520bf, 0xf7e44942, 0xa27e2a58, 0x66866fc5, 0x12519ce7, 0x437a8456,
];

impl<H: HashFunction> BloomFilter<H> {
    /// Creates a new Bloom filter with the specified table size, hash function, and number of hash functions.
    pub fn new(table_size: usize, hash_func: H, num_functions: usize) -> Option<Self> {
        if num_functions > SALTS.len() {
            return None;
        }

        let table_size_bytes = (table_size + 7) / 8;
        let table = vec![0; table_size_bytes];

        Some(BloomFilter {
            hash_func,
            table,
            table_size,
            num_functions,
        })
    }

    /// Inserts a value into the Bloom filter.
    pub fn insert(&mut self, value: &[u8]) {
        let hash = self.hash_func.hash(value);

        for i in 0..self.num_functions {
            let subhash = hash ^ SALTS[i];
            let index = (subhash % self.table_size as u32) as usize;
            let byte_index = index / 8;
            let bit_index = index % 8;
            self.table[byte_index] |= 1 << bit_index;
        }
    }

    /// Queries the Bloom filter to check if a value might be present.
    pub fn query(&self, value: &[u8]) -> bool {
        let hash = self.hash_func.hash(value);

        for i in 0..self.num_functions {
            let subhash = hash ^ SALTS[i];
            let index = (subhash % self.table_size as u32) as usize;
            let byte_index = index / 8;
            let bit_index = index % 8;
            if (self.table[byte_index] & (1 << bit_index)) == 0 {
                return false;
            }
        }

        true
    }

    /// Reads the Bloom filter's table into a provided buffer.
    pub fn read(&self, buffer: &mut [u8]) {
        let array_size = (self.table_size + 7) / 8;
        buffer.copy_from_slice(&self.table[..array_size]);
    }

    /// Loads the Bloom filter's table from a provided buffer.
    pub fn load(&mut self, buffer: &[u8]) {
        let array_size = (self.table_size + 7) / 8;
        self.table[..array_size].copy_from_slice(buffer);
    }

    /// Computes the union of two Bloom filters.
    pub fn union(&self, other: &Self) -> Option<Self> {
        if self.table_size != other.table_size
            || self.num_functions != other.num_functions
            || self.hash_func.hash(b"test") != other.hash_func.hash(b"test")
        {
            return None;
        }

        let mut result = Self::new(self.table_size, self.hash_func.clone(), self.num_functions)?;
        for i in 0..self.table.len() {
            result.table[i] = self.table[i] | other.table[i];
        }

        Some(result)
    }

    /// Computes the intersection of two Bloom filters.
    pub fn intersection(&self, other: &Self) -> Option<Self> {
        if self.table_size != other.table_size
            || self.num_functions != other.num_functions
            || self.hash_func.hash(b"test") != other.hash_func.hash(b"test")
        {
            return None;
        }

        let mut result = Self::new(self.table_size, self.hash_func.clone(), self.num_functions)?;
        for i in 0..self.table.len() {
            result.table[i] = self.table[i] & other.table[i];
        }

        Some(result)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestHashFunction;

    impl HashFunction for TestHashFunction {
        fn hash(&self, value: &[u8]) -> u32 {
            value.iter().fold(0, |acc, &x| acc.wrapping_add(x as u32))
        }
    }

    #[test]
    fn test_bloom_filter_insert_and_query() {
        let mut filter = BloomFilter::new(100, TestHashFunction, 4).unwrap();
        filter.insert(b"hello");
        assert!(filter.query(b"hello"));
        assert!(!filter.query(b"world"));
    }

    #[test]
    fn test_bloom_filter_union() {
        let mut filter1 = BloomFilter::new(100, TestHashFunction, 4).unwrap();
        let mut filter2 = BloomFilter::new(100, TestHashFunction, 4).unwrap();

        filter1.insert(b"hello");
        filter2.insert(b"world");

        let union = filter1.union(&filter2).unwrap();
        assert!(union.query(b"hello"));
        assert!(union.query(b"world"));
    }

    #[test]
    fn test_bloom_filter_intersection() {
        let mut filter1 = BloomFilter::new(100, TestHashFunction, 4).unwrap();
        let mut filter2 = BloomFilter::new(100, TestHashFunction, 4).unwrap();

        filter1.insert(b"hello");
        filter2.insert(b"hello");

        let intersection = filter1.intersection(&filter2).unwrap();
        assert!(intersection.query(b"hello"));
        assert!(!intersection.query(b"world"));
    }
}
